#pragma once 
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
enum State {
    EMPTY,
    DELETE,
    EXIST
};

template <class K, class V>
struct HashDate {
    pair<K, V> _kv;
    State _state = EMPTY;
};

template <class K, class V>
class HashTable {
    public:
        inline unsigned long __stl_next_prime(unsigned long n) {
            static const int __stl_num_primes = 28;
            static const unsigned long __stl_prim_list[__stl_num_primes] = {
                53, 97, 193, 389, 769,
			    1543, 3079, 6151, 12289, 24593,
			    49157, 98317, 196613, 393241, 786433,
			    1572869, 3145739, 6291469, 12582917, 25165843,
			    50331653, 100663319, 201326611, 402653189, 805306457,
			    1610612741, 3221225473, 4294967291
            };
            const unsigned long* first = __stl_prim_list;
            const unsigned long* last = __stl_prim_list + __stl_num_primes;
            const unsigned long* pos = lower_bound(first, last, n);
            return pos == last ? *(last - 1) : *pos;
        }
        bool Insert(const pair<K, V>& kv) {
            if(Find(kv.first)) {
                return false;
            }
            if(_n * 10 / _table.size() >= 7) {
                HashTable<K, V> newHashTable;
                newHashTable._table.resize(__stl_next_prime(_table.size() + 1));
                for(auto& d : _table) {
                    if(d._state == EXIST) {
                        newHashTable.Insert(d._kv);
                    }
                }
                _table.swap(newHashTable._table);
            }
            size_t hash0 = kv.first % _table.size(); // 哈希函数的地址
            size_t hashi = hash0; // 最终的插入位置
            size_t i = 1;
            int falg = 1;
            while(_table[hashi]._state == EXIST) {
                // 线性探测
                hashi = (hash0 + i) % _table.size();
                i++;
            }
            _table[hashi]._kv = kv;
            _table[hashi]._state = EXIST;
            _n++;
            return true;
        }
        HashDate<K, V>* Find(const K& key) {
            size_t hash0 = key % _table.size();
            size_t hashi = hash0;
            size_t i = 1;
            while(_table[hashi]._state != EMPTY) {
                if(_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {
                    return &_table[hashi];
                }
                hashi = (hash0 + i) % _table.size();
                i++;
            }
            return nullptr;
        }
        bool Erase(const K& key) {
            HashDate<K, V>* pos = Find(key);
            if(pos) {
                pos->_state = DELETE;
                _n--;
                return true;
            }
            return false;
        }
    private:
        vector<HashDate<K, V>> _table;
        size_t _n = 0; // 记录数据的个数
};